using namespace std;
#include<iostream>
#include<string>
#include<queue>
//class Solution {
//public:
//    string tree2str(TreeNode* root) {
//        if (root == nullptr)
//            return "";
//        string ret = to_string(root->val);
//        if (root->left || root->right) {
//            ret += "(";
//            ret += tree2str(root->left);
//            ret += ")";
//        }
//        if (root->right)
//        {
//            ret += "(";
//            ret += tree2str(root->right);
//            ret += ")";
//        }
//        return ret;
//    }
//};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {

        vector<vector<int>> ret;
        if (nullptr == root)
            return ret;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {

            vector<int> level;
            int levelSize = q.size();


            for (size_t i = 0; i < levelSize; ++i)
            {
                TreeNode* pCur = q.front();
                level.push_back(pCur->val);


                if (pCur->left)
                    q.push(pCur->left);

                if (pCur->right)
                    q.push(pCur->right);

                q.pop();
            }

            ret.push_back(level);
        }

        return ret;
    }
};


class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if (nullptr == root)
            return ret;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty())
        {

            vector<int> level;
            int levelSize = q.size();


            for (size_t i = 0; i < levelSize; ++i)
            {
                TreeNode* pCur = q.front();
                level.push_back(pCur->val);


                if (pCur->left)
                    q.push(pCur->left);

                if (pCur->right)
                    q.push(pCur->right);

                q.pop();
            }

            ret.push_back(level);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
class Solution {
public:
    bool IsInTree(TreeNode* root, TreeNode* x)
    {
        if (root == nullptr)
        {
            return false;
        }
        return root == x
            || IsInTree(root->left, x)
            || IsInTree(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == NULL)
        {
            return NULL;
        }
        if (root == p || root == q) {
            return root;
        }
        bool pInLeft, pInRight, qInLeft, qInRight;

        pInLeft = IsInTree(root->left, p);
        pInRight = !pInLeft;

        qInLeft = IsInTree(root->left, q);
        qInRight = !qInLeft;

        if ((pInLeft && qInRight) || (qInLeft && pInRight))
        {
            return root;
        }
        else if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (qInRight && pInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        assert(false);
        return NULL;
    }
};
class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if (root == nullptr)
        {
            return false;
        }
        path.push(root);
        if (root == x)
        {
            return true;
        }
        if (GetPath(root->left, x, path))
        {
            return true;
        }
        if (GetPath(root->right, x, path))
        {
            return true;
        }
        path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else {
                qPath.pop();
            }
        }
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};

class Solution {
public:
    void InOrderConvert(TreeNode* root, TreeNode*& prev)
    {
        if (root == nullptr) {
            return;
        }
        InOrderConvert(root->left, prev);
        root->left = prev;
        if (prev) {
            prev->right = root;
        }
        prev = root;
        InOrderConvert(root->right, prev);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
        InOrderConvert(pRootOfTree, prev);
        TreeNode* head = pRootOfTree;
        while (head && head->left) {
            head = head->left;
        }
        return head;
    }
};

int main()
{
	queue<int> q;

	return 0;
}